//
// Created by lanlu on 2025/8/8.
//

#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};


class Solution {
public:
    // 获取从根节点到指定节点的路径
    // 返回是否成功找到
    bool getPath(TreeNode * root, TreeNode * target, vector<TreeNode *> & path)
    {
        if (root == nullptr) return false;
        // 先将当前节点加入路径
        path.push_back(root);
        // 找到目标 路径完成
        if (root == target) return true;
        // 如果在左右子树中找到了目标节点 则返回true
        if (getPath(root->left, target, path) || getPath(root->right, target, path))
        {
            return true;
        }
        // 如果没有找到则返回false 删除当前节点
        path.pop_back();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode *> pPath, qPath;
        getPath(root, p, pPath);
        getPath(root, q, qPath);
        // 找最后一个公共节点
        TreeNode * lca = nullptr;
        for (int i = 0; i < pPath.size() && i < qPath.size(); i++)
        {
            if (pPath[i] == qPath[i])
            {
                lca = pPath[i];
            }
            else
            {
                // 不相等 直接退出
                break;
            }
        }
        return lca;
    }
};
